#include <iostream>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.
 * */
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
	{
	}
};

class Solution {
	void morris_travel(TreeNode *root, vector<int> &path)
	{
		TreeNode *cur = root;
		TreeNode *mostright = nullptr;
		while (cur) {
			if (cur->left) {
				mostright = cur->left;
				while (mostright->right != nullptr && mostright->right != cur) {
					mostright = mostright->right;
				}
				if (mostright->right == nullptr) {
					path.push_back(cur->val);
					mostright->right = cur;
					cur = cur->left;
				} else {
					mostright->right = nullptr;
					cur = cur->right;
				}
			} else {
				path.push_back(cur->val);
				cur = cur->right;
			}
		}
	}

    public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		vector<int> path;
		morris_travel(root, path);
		return path;
	}
};

TreeNode *create_tree(int p, vector<int> &root)
{
	if (p >= root.size() || root[p] == -1) {
		return nullptr;
	}
	TreeNode *left = create_tree(((p + 1) << 1) - 1, root);
	TreeNode *right = create_tree((p + 1) << 1, root);
	return new TreeNode(root[p], left, right);
}

int main()
{
	vector<int> root = { 1, 2, 3, 4, 5, -1, 8, -1, -1, 6, 7, 9 };
	TreeNode *t = create_tree(0, root);
	vector<int> path = Solution().preorderTraversal(t);
	for (auto v : path) {
		cout << v << ' ';
	}
	cout << endl;
	return 0;
}